/*
 * @lc app=leetcode id=200 lang=cpp
 *
 * [200] Number of Islands
 */
class Solution {
public:
    char direct[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    bool canMove(int i, int j, int row, int col, int mi, int mj) {
        return ((i+mi)>=0 && (i+mi)<row) && ((j+mj) >= 0 && (j+mj)<col);
    }
    int numIslands(vector<vector<char>>& grid) {
        int cnt = 0;
        int row = grid.size();
        if (row < 1) {
            return cnt;
        }
        int col = grid[0].size();
        if (col < 1) {
            return cnt;
        } 

        vector<vector<bool>> visited(row);
        for (int i=0; i<row; i++) {
            visited[i] = vector<bool>(col, false);
        }

        for (int i=0; i < row; i++) {
            for (int j=0; j<col; j++) {
                if (!visited[i][j] && grid[i][j]=='1') {
                    detect(grid, visited, row, col, i, j);
                    cnt ++;
                }
            }
        }
        
        return cnt;
    }

    void detect(vector<vector<char>>& grid, vector<vector<bool>>& visited, int row, int col, int i, int j) {
        if (visited[i][j]) {
            return;
        }

        visited[i][j] = true;
        for (auto dir:direct) {
            int mi = dir[0];
            int mj = dir[1];
            if (canMove(i,j,row,col,mi,mj) && !visited[i+mi][j+mj] && grid[i+mi][j+mj] == '1') {
                detect(grid, visited, row, col, i+mi, j+mj);
            }
        }
    }
};

